//
// Created by user on 2022/3/22.
//

#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int sum=0;
void preorder(TreeNode * root, TreeNode* parent){
    if(!root)return;

    if(!root->left && !root->right && parent->left==root){
        sum+=root->val;
    }
    preorder(root->left, root);
    preorder(root->right, root);
}

int sumOfLeftLeaves(TreeNode* root) {
    if(!root)return sum;
    preorder(root, root);
    return sum;
}

// DFS 后序遍历
int postOrder(TreeNode* node, TreeNode* parent) {
    if (!node) return 0;

    if (!node->left && !node->right && parent->left == node) {
        return node->val;
    }

    int leftLeavesSum = postOrder(node->left, node);
    int rightLeavesSum = postOrder(node->right, node);

    return leftLeavesSum + rightLeavesSum;
}
int sumOfLeftLeaves1(TreeNode* root) {
    return postOrder(root, root);
}


// BFS
bool isLeafNode(TreeNode* node) {
    return !node->left && !node->right;
}
int sumOfLeftLeaves3(TreeNode* root) {
    if (!root) return 0;

    int sum;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode *curr = q.front();
            q.pop();

            if (curr->left) {
                if (isLeafNode(curr->left)) {
                    sum += curr->left->val;
                } else {
                    q.push(curr->left);
                }
            }
            if (curr->right && !isLeafNode(curr->right)) q.push(curr->right);
        }
    }

    return sum;
}

